package ljl.alg.jianzhioffer.round2;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * "abaccdeff" -> b
 * */
public class _50_first_uniq_char {
    
    // 先试试 linked hash map
    // 通过了，可以
    public char firstUniqChar1(String s) {
        LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (Map.Entry<Character, Integer> each : map.entrySet()) {
            if (each.getValue() == 1)
                return each.getKey();
        }
        return ' ';
    }
    
    /*
    * 这道题显然在考察滑动窗口吧？
    * 不也是一个 map 加一个链表？也是 linked hash map！
    *
    * 是不是想复杂了？
    *
    * */
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        LinkedList<Character> queue = new LinkedList<>();
        // 我思路是先往 map 里怼，如果不存在就进队列，存在就算了
        // 然后从左边开始出队列，碰到单个的就停止
        // leetcode
        for (char c : s.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 1);
                queue.offer(c);
            } else {
                map.put(c, map.get(c) + 1);
            }
            while (!queue.isEmpty() && map.get(queue.peek()) > 1) {
                queue.poll();
            }
        }
        return queue.isEmpty() ? ' ' : queue.peekFirst();
    }
    
    public char firstUniqChar3(String s) {
        Map<Character, Boolean> map = new LinkedHashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, !map.containsKey(c));
        }
        for (Map.Entry<Character, Boolean> each : map.entrySet()) {
            if (each.getValue()) return each.getKey();
        }
        return ' ';
    }
    
    // 还有一种 hash 表保存所有字符出现次数，然后遍历字符串，挨个判断，不写了，没意思
}
